package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2020/7/10 10:31
 */
public class Rain {
    /**
     * 接雨水
     */
    @Test
    public void trap() {
        Assert.assertEquals(6, trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));
        Assert.assertEquals(7, trap(new int[]{0, 1, 0, 2, 0, 0, 1, 3, 2, 1, 2, 1}));
    }

    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        int max = height[0];
        for (int i = 1; i < height.length; i++) {
            max = Math.max(max, height[i]);
        }
        int sum = max * height.length;
        int[] starts = new int[max + 1], ends = new int[max + 1];
        for (int i = 0; i < max; i++) {
            starts[i] = -1;
            ends[i] = -1;
        }
        int left = 0, right = height.length - 1;
        while (left < right) {
            sum -= (height[left] + height[right]);
            if (starts[height[left]] == -1) {
                for (int i = 0; i <= height[left]; i++) {
                    if (starts[i] == -1) {
                        starts[i] = left;
                        sum -= left;
                    }
                }
            }
            if (ends[height[right]] == -1) {
                for (int i = 0; i <= height[right]; i++) {
                    if (ends[i] == -1) {
                        sum -= height.length - 1 - right;
                        ends[i] = right;
                    }
                }
            }
            left++;
            right--;
        }
        return sum;
    }

    public int trap4(int[] height) {
        if (height.length == 0) {
            return 0;
        }
        int max = height[0];
        for (int i = 1; i < height.length; i++) {
            max = Math.max(max, height[i]);
        }
        int[] dp = new int[max], starts = new int[max], ends = new int[max];
        for (int i = 0; i < max; i++) {
            dp[i] = height.length;
            starts[i] = -1;
            ends[i] = -1;
        }
        for (int i = 0; i < height.length; i++) {
            for (int j = 0; j < height[i]; j++) {
                dp[j]--;
                if (starts[j] == -1) {
                    starts[j] = i;
                }
                ends[j] = i;
            }
        }
        int res = 0;
        for (int i = 0; i < max; i++) {
            res += dp[i] - starts[i] + ends[i] - height.length + 1;
        }
        return res;
    }

    public int trap3(int[] height) {
        int sum = 0;
        int[] maxLeft = new int[height.length];
        int[] maxRight = new int[height.length];

        for (int i = 1; i < height.length - 1; i++) {
            maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            maxRight[i] = Math.max(maxRight[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(maxLeft[i], maxRight[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }

    public int trap2(int[] height) {
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] == 0) {
                continue;
            }
            for (int k = 1; k <= height[i]; k++) {
                int j = i + 1;
                for (; j < height.length; j++) {
                    if (k <= height[j]) {
                        if (j > i + 1) {
                            res += j - i - 1;
                        }
                        break;
                    }
                }
            }
        }
        return res;
    }
}
